DROPS

Document

DOI: 10.4230/LIPIcs.STACS.2021.18

The Approximation Ratio of the 2-Opt Heuristic for the Euclidean Traveling Salesman Problem

Authors: Ulrich A. Brodowsky and Stefan Hougardy

Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)

Abstract

The 2-Opt heuristic is a simple improvement heuristic for the Traveling Salesman Problem. It starts with an arbitrary tour and then repeatedly replaces two edges of the tour by two other edges, as long as this yields a shorter tour. We will prove that for Euclidean Traveling Salesman Problems with n cities the approximation ratio of the 2-Opt heuristic is Θ(log n / log log n). This improves the upper bound of O(log n) given by Chandra, Karloff, and Tovey [Barun Chandra et al., 1999] in 1999.

Cite as

Ulrich A. Brodowsky and Stefan Hougardy. The Approximation Ratio of the 2-Opt Heuristic for the Euclidean Traveling Salesman Problem. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 18:1-18:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{brodowsky_et_al:LIPIcs.STACS.2021.18,
  author =	{Brodowsky, Ulrich A. and Hougardy, Stefan},
  title =	{{The Approximation Ratio of the 2-Opt Heuristic for the Euclidean Traveling Salesman Problem}},
  booktitle =	{38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)},
  pages =	{18:1--18:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-180-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{187},
  editor =	{Bl\"{a}ser, Markus and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.18},
  URN =		{urn:nbn:de:0030-drops-136634},
  doi =		{10.4230/LIPIcs.STACS.2021.18},
  annote =	{Keywords: traveling salesman problem, metric TSP, Euclidean TSP, 2-Opt, approximation algorithm}
}

Search Results

Documents authored by Hougardy, Stefan

The Approximation Ratio of the 2-Opt Heuristic for the Euclidean Traveling Salesman Problem

Abstract

Cite as

Thanks for your feedback!

Could not send message